// 分组背包(模版)
// 自01背包问世之后，小 A 对此深感兴趣
// 一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组
// 每组中的物品只能选择1件，现在他想知道最大的利用价值是多少
// 测试链接 : https://www.luogu.com.cn/problem/P1757
// 提交以下的所有代码，可以直接通过

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1001;
const int MAXM = 1001;
// arr[i][0] i号物品的体积
// arr[i][1] i号物品的价值
// arr[i][2] i号物品的组号
tuple<int, int, int> arr[MAXN];
// 也可以使用 vector<int> arr[MAXN];
// 也可以使用 array<int, 3> arr[MAXN];
int m, n;
int dp[MAXM];

// 严格位置依赖的动态规划
int compute1()
{
    int teams = 1;
    for(int i = 2; i <= n; ++i)
    {
        if(get<2>(arr[i]) != get<2>(arr[i - 1]))
        {
            ++teams;
        }
    }

    // 组的编号1~teams
    // dp[i][j] : 1~i是组的范围，每个组的物品挑一件，容量不超过j的情况下，最大收益
    // dp[0][....] = 0
    int dp[teams + 1][m + 1];
    memset(dp, 0, sizeof dp);
    for(int start = 1, end = 2, i = 1; i <= teams; ++i)
    {
        while(end <= n && get<2>(arr[end]) == get<2>(arr[start]))
        {
            ++end;
        }
        // start ... end-1 -> i组
        for(int j = 0; j <= m; ++j)
        {
            // arr[start...end-1]是当前组，组号一样
            // 其中的每一件商品枚举一遍
            dp[i][j] = dp[i - 1][j];
            // k是组内的一个商品编号
            for(int k = start; k < end; ++k)
            {
                if(j - get<0>(arr[k]) >= 0)
                {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - get<0>(arr[k])] + get<1>(arr[k]));
                }
            }
        }
        // start去往下一组的第一个物品
        // 继续处理剩下的组
        start = end++;
    }
    return dp[teams][m];
}

// 空间压缩
int compute2()
{
    // dp[0][...] = 0
    memset(dp, 0, sizeof dp);
    for(int start = 1, end = 2; start <= n;)
    {
        while(end <= n && get<2>(arr[end]) == get<2>(arr[start]))
        {
            ++end;
        }
        // start ... end-1 -> i组
        for(int j = m; j >= 0; --j)
        {
            for(int k = start; k < end; ++k)
            {
                if(j - get<0>(arr[k]) >= 0)
                {
                    dp[j] = max(dp[j], dp[j - get<0>(arr[k])] + get<1>(arr[k]));
                }
            }
        }
        start = end++;
    }
    return dp[m];
}

int main()
{
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= n; ++i)
    {
        // weight value group
        scanf("%d%d%d", &get<0>(arr[i]), &get<1>(arr[i]), &get<2>(arr[i]));
    }
    // 按照组号进行排序
    sort(arr + 1, arr + n + 1, [](auto& a, auto& b){
        return get<2>(a) < get<2>(b);
    });
    printf("%d\n", compute2());

    return 0;
}